package datastucture;
import java.util.LinkedList;
import java.util.ListIterator;


public class Polynomial extends LinkedList<Literal>{

	
	/**
	 * @author WangXuanyi 
	 * @since 2012.10.10~10.11
	 */
	private static final long serialVersionUID = 1L;

	public Polynomial(){
		
	}
	
	public Polynomial(String polynomial){
		for(String literal : polynomial.split("[+]")){
			this.add(new Literal(literal));
		}
	}
	
	public Polynomial add(Polynomial p){
		Polynomial sum = new Polynomial();
		ListIterator<Literal> lhsIterator = this.listIterator();
		ListIterator<Literal> rhsIterator = p.listIterator();
		Literal lhs = lhsIterator.next();
		Literal rhs = rhsIterator.next();
		while( lhs != null && rhs != null){
			if(lhs.exponent == rhs.exponent){
				if(lhs.coefficient + rhs.coefficient != 0){
					sum.add(new Literal(lhs.coefficient + rhs.coefficient, lhs.exponent));
				}
				if(lhsIterator.hasNext()&&rhsIterator.hasNext()){
					lhs = lhsIterator.next();
					rhs = rhsIterator.next();
				}
				else{
					lhs = null;
					rhs = null;
				}
			}
			else if(lhs.exponent > rhs.exponent){
				sum.add(lhs);
				if(lhsIterator.hasNext()){
					lhs = lhsIterator.next();
				}else{
					lhs = null;
				}
			}
			else if(lhs.exponent < rhs.exponent){
				sum.add(rhs);
				if(rhsIterator.hasNext()){
				rhs = rhsIterator.next();
				}else{
					rhs = null;
				}
			}
		}
		for(;lhsIterator.hasNext();){
			sum.add(lhsIterator.next());
		}
		for(;rhsIterator.hasNext();){
			sum.add(rhsIterator.next());
		}
		return sum;
	}
	
	public void printList(){
		ListIterator<Literal> itr = this.listIterator();
		String output = "";
		
		while(itr.hasNext()){
			Literal temp = itr.next();
			if(temp.exponent > 1){
				if(temp.coefficient != 1)
					output += temp.coefficient + "x^" + temp.exponent;
				else
					output += "x^" + temp.exponent;
			}
			else if(temp.exponent == 1){
				if(temp.coefficient != 1)
					output += temp.coefficient + "x";
				else
					output += "x";
			}else{
				output += temp.coefficient;
			}
			if(itr.hasNext()){
				output += "+";
			}
		}
		
		System.out.println(output);
		
	}
	
}

class Literal{
	
	int coefficient;
	int exponent;
	
	public Literal(){
		
	}
	
	public Literal(int coefficient, int exponent){
		this.coefficient = coefficient;
		this.exponent = exponent;
	}
	
	public Literal(String s){
		if(s.contains("x^")){
			if(s.startsWith("x")){
				this.coefficient = 1;
				this.exponent = Integer.parseInt(s.replace("x^", ""));
			}
			else{
				this.coefficient = Integer.parseInt(s.split("x\\^")[0]);
				this.exponent = Integer.parseInt(s.split("x\\^")[1]);
			}
		}
		else if(s.contains("x")){
			if(s.startsWith("x")){
				this.coefficient = 1;
			}
			else{
				this.coefficient = Integer.parseInt(s.split("x")[0]);
			}
			this.exponent = 1;
		}
		else{
			this.coefficient = Integer.parseInt(s);
			this.exponent = 0;
		}
	}
}
